Динамическое программирование — метод оптимизации, использующий разбиение задачи на перекрывающиеся подзадачи и сохранение их решений.

• Два подхода: топ-даун (мемоизация) и боттом-ап (табличный).

• Ключ: формулировка рекуррентного соотношения и выбор состояния.

• Сложность часто O(n·m) для двумерных состояний; память можно оптимизировать, если зависимости линейны.

Примеры: числа Фибоначчи, рюкзак, LCS, редактирующее расстояние, пути в графе (Floyd-Warshall).